//
// Description: 欧几里得算法 模板
// Created by Loading on 2022/5/24.
//

/* 适用于求两个非负整数的最大公约数 */

/*
 * 欧几里得算法又称辗转相除法。
 * 算法思想：a 和 b 的最大公约数等于 b 和 a mod b 的最大公约数相同
 * 证明：a % b = a - kb，k 为 a / b 下取整
 * 若 d 是(a, b)的公约数，则 d 能被 a 整除，也能被 b 整除，故 d 也能被 a - kb 整除
 * 若 d 是(b, a % b)的公约数，则 d 能被 b 整除，也能被 a - kb 整除，故 d 也能被 a - kb + kb = a 整除
 * 因此，(a, b)的公约数集合与(b, a % b)的公约数集合一致，所以他们的最大公约数也相同
 */

#include <bits/stdc++.h>

using namespace std;

/* 时间复杂度：O(logn) */
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main() {

    return 0;
}